package algorithmlearn.strmatch;

//回溯算法 和 动态规划实现  编辑距离算法
//
//编辑距离指的就是，
// 将一个字符串转化成另一个字符串，
// 需要的最少编辑操作次数（比如增加一个字符、删除一个字符、替换一个字符）。
// 编辑距离越大，说明两个字符串的相似程度越小；
// 相反，编辑距离就越小，
// 说明两个字符串的相似程度越大。对于两个完全相同的字符串来说，编辑距离就是 0。

//比较著名的有莱文斯坦距离（Levenshtein distance）和最长公共子串长度（Longest common substring length）。
// 其中，莱文斯坦距离允许增加、删除、替换字符这三个编辑操作，
// 最长公共子串长度只允许增加、删除字符这两个编辑操作。
//下面 对这两种方式实现
public class EditDistance {
    private char[] xchars = {};
    private char[] ychars = {};
    private int minDist = Integer.MAX_VALUE; // 存储结果

    //backtracking 回溯实现
    public int matchBT(String x, String y) {
        xchars = x.toCharArray();
        ychars = y.toCharArray();
        minDist = Integer.MAX_VALUE;
        this.lwstBT(0, 0, 0);
        return minDist;
    }
//莱文斯坦距离1 bt实现
    private void lwstBT(int i, int j, int edist) {
        if (i == xchars.length || j == ychars.length) {
            if (i < xchars.length) edist += (xchars.length - i);
            if (j < ychars.length) edist += (ychars.length - j);
//            System.out.println(minDist + " --- " +  edist);
            minDist = Math.min(minDist, edist);
            return;
        }
        if (xchars[i] == ychars[j]) {
            lwstBT(i + 1, j + 1, edist);
        } else {
            lwstBT(i, j + 1, edist + 1); // 删除 b[i] 或者 a[j] 前添加一个字符
            lwstBT(i + 1, j, edist + 1);// 删除 a[i] 或者 b[j] 前添加一个字符
            lwstBT(i + 1, j + 1, edist + 1);// 将 a[i] 和 b[j] 替换为相同字符
        }
    }
//莱文斯坦距离2  dp实现
    public int mactchDP(String x, String y) {
        xchars = x.toCharArray();
        ychars = y.toCharArray();
        int m = xchars.length;
        int n = ychars.length;
        int[][] minDist = new int[m][n];
        for (int i = 0; i < n; ++i) { // 初始化第 0 行:a[0..0] 与 b[0..j] 的编辑距离
            if (xchars[0] == ychars[i]) minDist[0][i] = i;
            else if (i != 0) minDist[0][i] = minDist[0][i - 1] + 1;
            else minDist[0][i] = 1;
        }
        for (int j = 0; j < m; ++j) { // 初始化第 0 列:a[0..i] 与 b[0..0] 的编辑距离
            if (xchars[j] == ychars[0]) minDist[j][0] = j;
            else if (j != 0) minDist[j][0] = minDist[j - 1][0] + 1;
            else minDist[j][0] = 1;
        }
        for (int i = 1; i < m; ++i) { // 按行填表
            for (int j = 1; j < n; ++j) {
                if (xchars[i] == ychars[j]) minDist[i][j] =
                        min(minDist[i - 1][j] + 1, minDist[i][j - 1] + 1, minDist[i - 1][j - 1]);
                else minDist[i][j] =
                        min(minDist[i - 1][j] + 1, minDist[i][j - 1] + 1, minDist[i - 1][j - 1] + 1);
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(minDist[i][j] + " ");
            }
            System.out.println();
        }
        return minDist[m - 1][n - 1];
    }
    private int min(int a, int b, int c) {
        int min = Integer.MAX_VALUE;
        if (a < min) min = a;
        if (b < min) min = b;
        if (c < min) min = c;
        return min;
    }

//最长公共子串长度  dp实现
public int lcs(char[] a, int n, char[] b, int m) {
    int[][] maxlcs = new int[n][m];
    for (int j = 0; j < m; ++j) {// 初始化第 0 行：a[0..0] 与 b[0..j] 的 maxlcs
        if (a[0] == b[j]) maxlcs[0][j] = 1;
        else if (j != 0) maxlcs[0][j] = maxlcs[0][j-1];
        else maxlcs[0][j] = 0;
    }
    for (int i = 0; i < n; ++i) {// 初始化第 0 列：a[0..i] 与 b[0..0] 的 maxlcs
        if (a[i] == b[0]) maxlcs[i][0] = 1;
        else if (i != 0) maxlcs[i][0] = maxlcs[i-1][0];
        else maxlcs[i][0] = 0;
    }
    for (int i = 1; i < n; ++i) { // 填表
        for (int j = 1; j < m; ++j) {
            if (a[i] == b[j]) maxlcs[i][j] = max(
                    maxlcs[i-1][j], maxlcs[i][j-1], maxlcs[i-1][j-1]+1);
            else maxlcs[i][j] = max(
                    maxlcs[i-1][j], maxlcs[i][j-1], maxlcs[i-1][j-1]);
        }
    }
    return maxlcs[n-1][m-1];
}

    private int max(int x, int y, int z) {
        int maxv = Integer.MIN_VALUE;
        if (x > maxv) maxv = x;
        if (y > maxv) maxv = y;
        if (z > maxv) maxv = z;
        return maxv;
    }


    public static void main(String[] args) {
        EditDistance editDistance = new EditDistance();

        System.out.println("回溯实现：编辑距离: ");
        editDistance.matchBT("abbdcdfdasewasdds", "bbcdcfsdsdsdsddds");
        System.out.println(editDistance.minDist);
        System.out.println("动态规划实现：编辑距离: ");
        int i = editDistance.mactchDP("abbdcdfdasewasdds", "bbcdcfsdsdsdsddds");
        System.out.println(i);
    }
}
